---
id: 5900f50c1000cf542c51001e
title: 'Завдання 415: титанічні множини'
challengeType: 1
forumTopicId: 302084
dashedName: problem-415-titanic-sets
---

# --description--

Множина точок сітки $S$ називається титанічною множиною, якщо між двома точками цієї множини проходить пряма.

Прикладом титанічної множини є $S = \\{(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)\\}$, де між (0, 1) та (2, 0) проходить пряма, яка не проходить через будь-які інші точки в $S$.

З іншого боку, множина {(0, 0), (1, 1), (2, 2), (4, 4)} не є титанічною множиною, оскільки пряма, що проходить через дві точки у множині, також проходить через дві інші.

Нехай $T(N)$ з додатним значенням $N$ буде кількістю титанічних множин $S$, кожна точка ($x$, $y$) яких задовільняє умову $0 ≤ x$, $y ≤ N$. Можна довести, що $T(1) = 11$, $T(2) = 494$, $T(4) = 33\\,554\\,178$, $T(111)\bmod {10}^8 = 13\\,500\\,401$ та $T({10}^5)\bmod {10}^8 = 63\\,259\\,062$.

Знайдіть $T({10}^{11})\bmod {10}^8$.

# --hints--

`titanicSets()` має повернути `55859742`.

```js
assert.strictEqual(titanicSets(), 55859742);
```

# --seed--

## --seed-contents--

```js
function titanicSets() {

  return true;
}

titanicSets();
```

# --solutions--

```js
// solution required
```
